package com.example.demo;

import org.junit.jupiter.api.Test;

public class ReviewPractice {



    public static void sys(int nums[]){
        for(int i=0;i<nums.length;i++){
            System.out.println(nums[i]);
        }
    }
    /**
     * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
     *
     * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
     *
     * 注意：给定 n 是一个正整数。
     *
     * 示例 1：
     *
     * 输入：2
     * 输出：2
     * 解释： 有两种方法可以爬到楼顶。
     *
     * 1. 1 阶 + 1 阶
     * 2. 2 阶
     * 示例 2：
     *
     * 输入：3
     * 输出：3
     * 解释： 有三种方法可以爬到楼顶。
     *
     * 1. 1 阶 + 1 阶 + 1 阶
     * 2. 1 阶 + 2 阶
     * 3. 2 阶 + 1 阶
     */

    /**
     *
     * @param n
     * @return
     */
    public static int loop(int n){
        if(n==0|| n<0){
            return 0;
        }
        // index 代表n value代表对应index的方法格式
        int [] dps = new int[n+1];
        dps[1] = 1;
        dps[2] = 2;
        for(int i=3;i<=n;i++){
            dps[i] = dps[i-1]+dps[i-2];
        }
        return dps[n];
    }

    /**
     * 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
     *
     * 示例:
     *
     * 输入: [-2,1,-3,4,-1,2,1,-5,4],
     * 输出: 6
     * 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
     */
    public static int returnLarge1(int nums[]){
        if(nums==null || nums.length==0){
            return -1; //or throw runTimeException
        }
        //value为以index结尾的和
        int result = 0;
        int dps[] = new int[nums.length];
        for(int n=1;n<nums.length;n++){
            dps[n] = Math.max(dps[n-1],0)+nums[n];
            result = dps[n]>result?dps[n]:result;
        }
        return result;
    }

    /**
     * 给定一个无序的整数数组，找到其中最长上升子序列的长度。
     *
     * 示例:
     *
     * 输入: [10,9,2,5,3,7,101,18]
     * 输出: 4
     * 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
     */

    public static int testlargeSort(int nums[]){
        if(nums==null || nums.length==0){
            return 0;
        }
        int result = 0;
        int dps[] = new int[nums.length];
        dps[0] = 1;
        for(int i=1;i<nums.length;i++){
            dps[i] = dps[i-1]+(nums[i]>nums[i-1]?1:0);
            result = result>dps[i]?result:dps[i];
        }
        return result;
    }

    /**
     * 二分查找
     */

    public static int  binarySearch(int [] nums ,int target){
        if(nums == null || nums.length==0){
            return -1;
        }
        int start = 0;
        int end = nums.length-1;
        while(end>start){
            int middle = start+((end-start)>>>1);
            if (nums[middle]==target) {
                return middle;
            }else if(nums[middle]>target){
                end = middle-1;
            }else {
                start = middle+1;
            }
        }
        return -1;
    }

    public static int diguiSearch(int [] nums,int target){
        if(nums==null || nums.length==0){
            return -1;
        }
        int start = 0;
        int end = nums.length-1;
        return diguiSearch(nums,start,end,target);
    }

    private static int diguiSearch(int [] nums,int start, int end, int target) {
        if(end<=start){
            return -1;
        }

        int middle = start+((end-start)>>>1);
        if(nums[middle]==target){
            return middle;
        }else if(nums[middle]>target) {
            return diguiSearch(nums,start,middle-1,target);
        }else {
           return diguiSearch(nums,middle+1,end,target);
        }
    }

    /**
     * 6.2 全排列问题
     * 问题描述：
     *   有1，2，3，4个数，问你有多少种排列方法，并输出排列。
     */
    public static void sysAll(int nums[],int start ,int end){
        if(nums==null || nums.length==0){
            return;
        }
        if(start == end ){
            for(int temp:nums){
                System.out.print(temp);
            }
            System.out.println();
        }
        //全排列  123
        /**
         *  1 2 3   2 3  3   start end  start+1 end
         *  1 3 2
         *  2 1 3
         *  2 3 1
         *  3 1 2
         *  3 2 1
         */
        for(int i=start;i<=end;i++){
            swap(nums,i,start);
            sysAll(nums,start+1,end);
            swap(nums,i,start);
        }

    }

    public static void swap(int nums[], int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public static void quickSort(int nums[]){
        if(nums==null || nums.length==0){
            return;
        }
        int start = 0;
        int end = nums.length-1;

        quickSort(nums,start,end);
    }

    private static void quickSort(int[] nums, int start, int end) {
        if(end<=start){
            return;
        }
        int middle = middleTwo(nums,start,end);
        quickSort(nums,start,middle-1);
        quickSort(nums,middle+1,end);

    }
    // 6 1 2 3 7 4 5 6 -> 6 1 2 3 4 7  6 -> 4 1 2 3 6 7

    public static int middle(int nums[],int start,int end){
        int standard = nums[start];
        int temp =start;
        for(int i=start+1;i<=end;i++){
            if(nums[i]<standard){
                temp++;
                swap(nums,i,temp);
            }
        }
        swap(nums,temp,start);
        return temp;
    }

    public static int middleTwo(int nums[],int start,int end){
        int standard = nums[start];
        int left = start;
        int right = end;
        while(true){
            while(nums[right]>=standard&&right>left){
                right--;
            }
            while(nums[left]<standard&&right>left){
                left++;
            }

            swap(nums,left,right);
            if(left == right){
                break;
            }
        }

        swap(nums,left,start);
        return left;
    }

    /**
     * 冒泡排序
     * // 5 6 7 1 4 10
     */
    public static void sort1(int nums[]){

        for(int i=0;i<nums.length;i++){
            boolean flag = true;
            for(int j=i+1 ;j<nums.length;j++){
                if(nums[i]>nums[j]){
                    flag = false;
                    swap(nums,i,j);
                }
            }
            if(flag){
                break;
            }
        }
    }

    /**
     * 选择排序
     * // 1 -1 2 3 4 5
     * // -1 1 2 3 4 5
     * // 1,-1,2,-2,3,4,5
     * // -1 1 2 -2 3 4 5
     * 找到最大的元素依次放到最前面
     */
    public static void selectSort(int nums[]){
        if(nums==null || nums.length==0){
            return;
        }

        for(int i=0;i<nums.length;i++){
            int minIndex  = i;
            for(int j=i;j<nums.length;j++){
                if(nums[minIndex]>nums[j]){
                    minIndex = j;
                }
            }
            swap(nums,i,minIndex);
        }
    }
    // int nums []= {10,2,3,4,5,6,7,11,2232,434345,1123};



    public static void sortOuji(int nums[]){
        if(nums==null || nums.length==0){
            return;
        }
        int temp = nums.length-1;
        for(int i=0;i<nums.length;){
            if(!isJi(nums[i])){
                swap(nums,i,temp);
                temp = temp-1;
                if(i==temp){
                    break;
                }
            }else {
                i++;
            }
        }
    }

    //类似指针 奇数放前 偶数放后
    public static void sortQuji1(int nums[]){
        if(nums==null || nums.length==0){
            return;
        }
        int left = 0;
        int right = nums.length-1;
        while(true){
            while(isJi(nums[left])&&left<right){
                left++;
            }
            while(!isJi(nums[right])&&left<right){
                right--;
            }
            swap(nums,left,right);
            if(left==right){
                break;
            }
        }
    }

    public static  boolean isJi(int num){
        boolean result = false;
        if(num%2!=0){
            result = true;
        }
        return result;
    }

    /**
     * 如何高效对有序数组/链表去重？ 返回去重之后的数组长度
     * 给定数组{0,0,1,1,1,2,3,3,3} 返回去重之后的数组长度
     */

    public static int getLength(int nums[]){
        if(nums==null || nums.length==0){
            return 0;
        }
        int slow = 0;
        int fast = 1;
        int length = nums.length;
        for(int i=0;i<nums.length;i++){
            if(nums[slow]==nums[fast]){
                length--;

            }
            if(fast+1< nums.length-1){
                slow++;
                fast++;
            }
        }

        return length;
    }

    public static void main(String[] args) {
        int arr1s[] = {2,2,3,4};
        int arr2s[] = { 1,3,4,5};
        int kLarge = findKLarge(arr1s, arr2s, 4);
        System.out.println(kLarge);
    }
    /**
     * 给定两个有序数组arr1和arr2，再给定一个整数K，返回所有数中第K小的数。
     * O(1)
     * int arr1s[] = {2,2,3,4};
     *   int arr2s[] = {1,3,4,5};
     *   int k = 3
     */



    public static int findKLarge(int []arrs1,int [] arrs2,int k){

        int i = 0;
        int j = 0;
        boolean flag = true;
        while( true){
            while(arrs1[i]>=arrs2[j] && k>j && j<arrs2.length &&i+j<k){
                flag = true;
                j++;
            }

            while(arrs1[i]<=arrs2[j] && k>i && i<arrs1.length &&i+j<k){
                flag = false;
                i++;
            }

            if(i+j==k){
                if(flag){
                    return arrs2[j];
                }else {
                    return arrs1[i];
                }
            }
        }

    }

    /**
     * 合并k的
     */

    /**
     * 二分查找 左边界（第一次出现） 右边界 （最后一次出现）
     * @param arrs1
     * @param arrs2
     * @param k
     * @return
     */
    // 1,2,2,2,3,4,5
    public static int findLeft(int nums[],int target){
        if(nums==null || nums.length==0){
            return -1;
        }
        int start = 0;
        int end = nums.length-1;
        int result = -1;
        while(end>=start){
            int middle = start+((end-start)>>>1);
            if(nums[middle]==target){
                result = middle;
                while(nums[middle-1]==target){
                    result = result-1;
                    middle = middle-1;
                }
                return result;
            }else if(nums[middle]>target){
                end = middle-1;
            }else {
                start = middle+1;
            }
        }
        return result;
    }

    public static int find(int [] nums ,int target){
        if(nums==null || nums.length==0 ){
            return -1;
        }
        // 1 2 3 4 5 6
        int start = 0;
        int end = nums.length-1;
        while(end>=start){
            int middle = start+((end-start)>>>1);
            if(nums[middle] == target){
                return middle;
            }else if(nums[middle]<target){
                start = middle+1;
            }else {
                end = middle-1;
            }
        }
        return -1;
    }

    @Test
    public void test(){
        int nums[] = {1,1,1,2,2,2,2,2,4,5,6,7,8,9};
        int i = findLeftIndex(nums, 0);
        System.out.println(i);
    }

    public static int findLeftIndex(int nums[],int target){
        if(nums==null || nums.length==0){
            return -1;
        }
        int result = 0;
        int left = 0;
        int right = nums.length;
        // 1 2 2 3 5 6
        while(left<right){
            int middle = left+((right-left)>>>1);
            if(nums[middle]==target){
                right = middle;
            }else if(nums[middle]<target){
                left = middle+1;
            }else if(nums[middle]>target){
                right = middle;
            }
        }
        if(left == nums.length){
            return -1;
        }else if(nums[left]!=target){
            return -1;
        }
        return left;
    }


    public static int findRightIndex(int nums[],int target){
        if(nums==null || nums.length==0){
            return -1;
        }

        int left = 0;
        int right = nums.length;
        // 1 2 2 3 4 4 5 6
        while(left<right){
            int middle = left+((right-left)>>>1);
            if(nums[middle]==target){
                left = middle+1;
            }else if(nums[middle]<target){
                left = middle+1;
            }else if(nums[middle]>target){
                right = middle;
            }
        }
        if(left==0){
            return -1;
        }
        if(nums[left-1]==target){
            return left-1;
        }else {
            return -1;
        }

    }

    @Test
    public void test1(){
        System.out.println(1>>>1);
    }

}


